import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import org.junit.Test;

public class MyTest {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        traceBack(ans, new ArrayList<Integer>(), nums, 0);
        return ans;
    }
    private void traceBack(List<List<Integer>> ans,List<Integer> curr,int[] nums,int idx){
        ans.add(new ArrayList<Integer>(curr));
        for(int i=idx;i<nums.length;i++){
            curr.add(nums[i]);
            traceBack(ans, curr, nums, i+1);
            curr.remove(curr.size()-1);
        }
    }
    
    public int[][] updateMatrix(int[][] mat) {
        Queue<int[]> queue=new LinkedList<int[]>();
        int m=mat.length;
        int n=mat[0].length;
        int[][] dist=new int[m][n];
        boolean[][] seen=new boolean[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j]==0){
                    queue.offer(new int[]{i,j});
                    seen[i][j]=true;
                }
            }
        }
        while(!queue.isEmpty()){
            int[] curr=queue.poll();
            if(curr[0]-1>=0&&!seen[curr[0]-1][curr[1]]){
                dist[curr[0]-1][curr[1]]=dist[curr[0]][curr[1]]+1;
                seen[curr[0]-1][curr[1]]=true;
                queue.offer(new int[]{curr[0]-1,curr[1]});
            }
            if(curr[1]-1>=0&&!seen[curr[0]][curr[1]-1]){
                dist[curr[0]][curr[1]-1]=dist[curr[0]][curr[1]]+1;
                seen[curr[0]][curr[1]-1]=true;
                queue.offer(new int[]{curr[0],curr[1]-1});
            }
            if(curr[0]+1<m&&!seen[curr[0]+1][curr[1]]){
                dist[curr[0]+1][curr[1]]=dist[curr[0]][curr[1]]+1;
                seen[curr[0]+1][curr[1]]=true;
                queue.offer(new int[]{curr[0]+1,curr[1]});
            }
            if(curr[1]+1<n&&!seen[curr[0]][curr[1]+1]){
                dist[curr[0]][curr[1]+1]=dist[curr[0]][curr[1]]+1;
                seen[curr[0]][curr[1]+1]=true;
                queue.offer(new int[]{curr[0],curr[1]+1});
            }
        }
        return dist;
    }
    
    public int orangesRotting(int[][] grid) {
        return 0;
    }

    @Test
    public void test(){
        int[] nums={1,2,3};
        System.out.println(subsets(nums));
    }
}
